package com.currentbp.Interesting.likou.complete;

import org.junit.Test;

/**
 * @author baopan
 * @createTime 2024-04-08 16:01:52
 */
public class T1139largest1BorderedSquare {
    /*

     */
    @Test
    public void t1() {
        System.out.println(largest1BorderedSquare(new int[][]{{1, 1, 1}, {1, 0, 1}, {1, 1, 1}}));
        System.out.println(largest1BorderedSquare(new int[][]{{1, 1, 0}, {0, 0, 0}, {0, 0, 0}}));
    }

    public int largest1BorderedSquare(int[][] grid) {
        if (grid == null || grid.length <= 0) {
            return 0;
        }

        for (int i = grid.length; i >= 1; i--) {
            boolean isGood = doSquare(grid, i);
            if (isGood) {
                return i * i;
            }
        }

        return 0;
    }

    private boolean doSquare(int[][] grid, int len) {
        for (int i = 0; i <= grid.length - len; i++) {
            for (int j = 0; j <= grid[0].length - len; j++) {
                boolean isGood = doEachSquare(grid, i, j, len);
                if (isGood) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean doEachSquare(int[][] grid, int startI, int startJ, int len) {
        //left
        for (int i = 0; i < len; i++) {
            if (grid[startI + i][startJ] != 1) {
                return false;
            }
        }
        //right
        for (int i = 0; i < len; i++) {
            if (grid[startI + i][startJ + len - 1] != 1) {
                return false;
            }
        }
        //top
        for (int i = 0; i < len; i++) {
            if (grid[startI][startJ + i] != 1) {
                return false;
            }
        }
        //down
        for (int i = 0; i < len; i++) {
            if (grid[startI + len - 1][startJ + i] != 1) {
                return false;
            }
        }
        return true;
    }
}
